package B刷题.排序;

import java.util.Random;

/**
 * @author wei.zhao
 * @description: 1985.找出数组中的第K大整数
 * @date 2022年11月03日 14:04
 */
public class Code04_KthLargestNumber {

    // 找出nums排序后nums.length-K索引位的数字
    public String kthLargestNumber(String[] nums, int k) {
        return sort(nums, 0, nums.length - 1, k);
    }

    private String sort(String[] nums, int l, int r, int k) {
        int[] result = partition(nums, l, r);
        if (nums.length - k >= result[0] && nums.length - k <= result[1]) {
            return nums[nums.length - k];
        } else if (nums.length - k < result[0]) {
            return sort(nums, l, result[0] - 1, k);
        } else {
            return sort(nums, result[1] + 1, r, k);
        }
    }

    private int[] partition(String[] arr, int l, int r) {
        Random random = new Random();
        int index = random.nextInt(r - l + 1) + l;
        String num = arr[index];
        int[] result = new int[2];
        int lp = l;
        int rp = r;
        for (int i = l; i <= rp; i++) {
            if (compare(arr[i], num) > 0) {
                swap(arr, i--, rp--);
            } else if (compare(arr[i], num) < 0) {
                swap(arr, i, lp++);
            }
        }
        result[0] = lp;
        result[1] = rp;
        return result;
    }

    void swap(String[] arr, int a, int b) {
        String temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


    int compare(String a, String b) {
        if (a.length() > b.length()) {
            return 1;
        } else if (a.length() < b.length()) {
            return -1;
        } else {
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) > b.charAt(i)) {
                    return 1;
                } else if (a.charAt(i) < b.charAt(i)) {
                    return -1;
                }
            }
            return 0;
        }
    }

}
